package com.example.algorithm.backtrcaking;

import java.util.ArrayList;
import java.util.List;

/**
 * @author : zhy
 * @since : 2022/8/24
 * 递增子序列
 */
public class Increment {

        private List<Integer> path = new ArrayList<>();
        private List<List<Integer>> res = new ArrayList<>();
        public List<List<Integer>> findSubsequences(int[] nums) {
            backtracking(nums,0);
            return res;
        }

        private void backtracking (int[] nums, int start) {
            if (path.size() > 1) {
                res.add(new ArrayList<>(path));
            }

            int[] used = new int[201];
            for (int i = start; i < nums.length; i++) {
                if (!path.isEmpty() && nums[i] < path.get(path.size() - 1) || (used[nums[i] + 100] == 1)) { continue; }
                used[nums[i] + 100] = 1;
                path.add(nums[i]);
                backtracking(nums, i + 1);
                path.remove(path.size() - 1);
            }
        }

    public static void main(String[] args) {
        Increment increment = new Increment();
        int []can={4,6,7,7};
        List<List<Integer>> subsequences = increment.findSubsequences(can);
        subsequences.stream().forEach(System.out::println);
    }
}
